In the reproduction of copies of an original from video image data created, for example, by electronic raster input scanning from an original document, one is faced with the limited resolution capabilities of the reproducing system and the fact the output devices, are mostly binary. This is particularly evident when attempting to reproduce halftones, lines and continuous tone images. Of course, an image data processing system may be tailored so as to offset the limited resolution capabilities of the reproducing apparatus used, but this is difficult due to the divergent processing needs required by the different types of image which may be encountered. In this respect, it should be understood that the image content of the original document may consist entirely of high frequency halftones, low frequency halftones, continuous tones, or line copy, or a combination, in some unknown degree, of some or all of the above. In the face of these possibilities, optimizing the image processing system for one image type in an effort to offset the limitations in the resolution capability of the reproducing apparatus used, may not be possible, requiring a compromise choice which may not produce acceptable results. Thus, for example, where one optimizes the system for low frequency halftones, it is often at the expense of degraded reproduction of high frequency halftones, or of line copy, and vice versa.
In U.S. Pat. No. 4,194,221 to Stoffel, this problem was addressed by applying a discrimination function instructing the image processing system as to the type of image data present and particularly, an auto correlation function to the stream of pixel data, to determine the existence of halftone image data. Such a function is expressed as: ##EQU1## where n=the bit or pixel number;
p=the pixel voltage value; and PA1 t=the pixel position in the data stream. PA1 p is the pixel value; and PA1 t=a pixel position in the block of T pixels selected.
Stoffel describes a method of processing automatically a stream of image pixels representing unknown combinations of high and low frequency halftones, continuous tones, and/or lines to provide binary level output pixels representative of the image. The described function is applied to the stream of image pixels and, for the portions of the stream that contained high frequency halftone image data, notes a large number of closely spaced peaks in the resultant signal. The correlator circuits described in Stoffel's embodiment, however, are very expensive, as they must provide a digital multiplication function. Accordingly, as a practical matter, Stoffel requires as a first step, reduction of the amount of data handled, by initially thresholding image data against a single threshold value, to reduce the image to a high contrast black or white image. However, depending on the selection of the threshold as compared to the intensity of the image, significant amounts of information may be lost in the thresholding process. For example, if the threshold level is set to distinguish in the middle of the intensity range, but the image has significant variations through the darker gray levels, the thresholded result does not indicate the variations. This results in an undesirable loss of image information. While it may be possible to vary the threshold value adaptively from original to original and from image area to image area, such algorithms tend to be complicated and work well only for a restricted class of images such as line images. In U.S. Pat. No. 4,811,115 to Lin et al, the auto correlation function is calculated for the stream of halftone image data at selected time delays which are predicted to be indicative of the image frequency characteristics, without prior thresholding. The arithmetic function used in that auto correlation system is an approximation of the auto correlation function using logical functions and addition, rather than the multiplication function used in U.S. Pat. No. 4,194,221 to Stoffel. Valleys in the resulting auto correlated function are detected to determine whether high frequency halftone image data is present.
GB 2,153,619A provides a similar determination of the type of image data. However in that case, a threshold is applied to the image data at a certain level, and subsequent to thresholding the number of transitions from light to dark within a small area is counted. The system operates on the presumption that data with a low number of transitions after thresholding is probably a high frequency halftone or continuous tone image. The thresholding step in this method has the same undesirable effect as described for Stoffel.
Of background interest in this area are U.S. Pat. No. 4,556,918 to Yamazaki et al. showing an arrangement assuming a periodicity of an area of halftone dots which are thresholded against an average value derived from the area to produce a density related video signal; U.S. Pat. No. 4,251,837 to Janeway, Ill. which shows the use of a three decision mode selection for determining threshold selection based on gradient constants for each pixel; U.S. Pat. No. 4,578,714 to Sugiura et al. which shos random data added to the output signal to eliminate pseudo-outlines; U.S. Pat. No. 4,559,563 to Joiner, Jr. suggests an adaptive prediction for compressing data based on a predictor which worked best for a previous pixel block; and U.S. Pat. No. 3,294,896 to Young, Jr. teaches the usefulness of thresholding in producing an image from a binary digital transmission system.
U.S. Pat. No. 4,509,195 to Nadler describes a method for binarization of a pattern wherein two concentric rings around a pixel are evaluated to determine contrast values, and the contrast values are used then to determine whether the pixel and the surrounding areas have a light or dark quality. U.S. Pat. No. 4,547,811 to Ochi et al. teaches a method of processing gray level values, depending on the density level of blocks of pixels, and their difference from a minimum or maximum value. The blocks are then processable by a halftone processing matrix depending on the difference value, U.S. Pat. No. 4,730,221 to Roetling discloses a screening technique where values of gray over an image are evaluated to determine a minimum and maximum level, in order to determine constant levels of gray. U.S. Pat. No. 4,736,253 to Shida discloses a method of producing a halftone dot by selectively comparing image signals with highlight and shadow reference values, for determination of the binarization process.
A particular problem noted in the use of the auto correlation function is the false characterization of a portion of the image as a halftone, when in fact it would be preferable for the image to be processed as a line image. Examples of this defect are noted particularly in the processing of Japanese Kanji characters and small Roman letters. In these examples, the auto correlation function may detect the image as halftones and process accordingly, instead of applying a common threshold through the character image. The described computations of auto correlation are one dimensional in nature, and this problem of false detection will occur whenever a fine pattern that is periodic in the scan line or fast scan direction is detected. In the same vein, shadow areas and highlight areas are often not detected as halftones, and are then processed with the application of a uniform threshold.
Another similar problem is in the detection of color halftones, which typically include the superposition of plural separations of image data, at selected frequencies, but having the screens processed at angles with respect to each of the other screens. Accordingly, the response obtained after auto correlation is not the same as a response from a black and white image having a single screen frequency.